package www.study.com;

//正则表达式匹配 https://leetcode.cn/problems/regular-expression-matching/
//详见二哥
public class code10 {
    public static void main(String[] args) {

    }

    /**
     * 字母 + *存在两种情况：
     * 1.一个字符都不匹配，直接跳过
     * 2.匹配s[i]，然后继续匹配下去
     */
    class Solution {
        public boolean isMatch(String s, String p) {
            int n = s.length();
            int m = p.length();
            boolean[][] f = new boolean[n + 1][m + 1];
            f[0][0] = true;
            for(int i = 0 ; i <= n ; i++){
                for(int j = 1 ; j <= m ; j++){
                    if(p.charAt(j - 1) == '*'){
                        if(i != 0 && (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1))){
                            f[i][j] = f[i - 1][j] || f[i][j - 2];
                        }else{
                            f[i][j] = f[i][j - 2];
                        }
                    }else if(i != 0 && (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1))){
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
            return f[n][m];
        }
    }
}
